package com.whosly.demo.benchmark.sortalgorithms.quick;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 快速排序的标准算法实现。
 *
 * 此种方式性能低， 不推荐
 * 此种方式在大数据量下(几十万以上)容易出现 java.lang.StackOverflowError， 不推荐
 *
 * @author fengyang
 * @date 2023/6/13 上午10:53
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
@Deprecated
public class QuickSortMethod0
        implements ISortingAlgorithms
{
    public QuickSortMethod0()
    {

    }

    @Override
    public int[] sorting(int[] arr)
    {
        // 只适合小数据量。内部采用了递归方式
        return sort_0(arr, 0, arr.length - 1);
    }

    /**
     * while 查找
     */
    public int[] sort_0(int[] arr, int left, int right) {
        // 如果只有一个元素，就结束递归。
        // 子数组长度为 1 时终止递归
        if (left >= right) {
            return arr;
        }

        int partitionIndex = partition_0(arr, left, right);

        //对左子数组进行快速排序
        sort_0(arr, left, partitionIndex - 1);
        //对右子数组进行快速排序
        sort_0(arr, partitionIndex + 1, right);

        return arr;
    }

    /* 哨兵划分 */
    private int partition_0(int[] arr, int left, int right) {
        // 以 nums[left] 作为基准数
        int i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= arr[left])
                j--;          // 从右向左找首个小于基准数的元素
            while (i < j && arr[i] <= arr[left])
                i++;          // 从左向右找首个大于基准数的元素
            swap(arr, i, j); // 交换这两个元素
        }
        swap(arr, i, left);  // 将基准数交换至两子数组的分界线
        return i;             // 返回基准数的索引
    }

    /* 元素交换 */
    private final void swap(int[] arr, int n, int m) {
        int tmp = arr[n];
        arr[n] = arr[m];
        arr[m] = tmp;
    }

}
